package chapter10;

/**
 * 链表
 */
public class LinkedList {

    /**
     * 反转链表
     *
     * @param node
     * @return
     */
    public static Node reverse(Node node) {
        // 模拟倒排,首先从尾部开始就是null
        // 思路是,将当前节点给到下一个
        // 1-2-3-4
        Node curr = null;
        while (node != null) {
            // 将下一个元素拿出来下一次遍历用
            Node temp = node.next;

            // 将curr的给到顺序遍历的节点的下一个
            // 比如
            // node遍历到1的时候,curr=1->null
            // node遍历到2的时候,curr=2->1->null
            node.next = curr;
            // 重置curr
            curr = node;

            // 赋值下一轮遍历
            node = temp;
        }
        return curr;
    }

    public static void push(Node node, int x) {
        Node curr = new Node();
        curr.key = x;
        curr.next = node.next;
        curr.prev = node;
        node.next = curr;
    }

    public static int pop(Node node) {
        if (node.next == null) {
            return -1;
        }
        int val = node.next.key;
        node.next = node.next.next;
        return val;
    }

    static class Node {
        public Node prev;
        public int key;
        public Node next;

        Node() {

        }

        Node(int val) {
            this.key = val;
        }
    }
}
